home *** CD-ROM | disk | FTP | other *** search
/ Computer Shopper 242 / Issue 242 - April 2008 - DPCS0408DVD.ISO / Software Money Savers / VirtualDub / Source / VirtualDub-1.7.7-src.7z / src / h / vd2 / system / vdstl.h < prev    next >
Encoding:
C/C++ Source or Header  |  2007-10-13  |  23.5 KB  |  922 lines
  1. //    VirtualDub - Video processing and capture application
  2. //    System library component
  3. //    Copyright (C) 1998-2004 Avery Lee, All Rights Reserved.
  4. //
  5. //    Beginning with 1.6.0, the VirtualDub system library is licensed
  6. //    differently than the remainder of VirtualDub.  This particular file is
  7. //    thus licensed as follows (the "zlib" license):
  8. //
  9. //    This software is provided 'as-is', without any express or implied
  10. //    warranty.  In no event will the authors be held liable for any
  11. //    damages arising from the use of this software.
  12. //
  13. //    Permission is granted to anyone to use this software for any purpose,
  14. //    including commercial applications, and to alter it and redistribute it
  15. //    freely, subject to the following restrictions:
  16. //
  17. //    1.    The origin of this software must not be misrepresented; you must
  18. //        not claim that you wrote the original software. If you use this
  19. //        software in a product, an acknowledgment in the product
  20. //        documentation would be appreciated but is not required.
  21. //    2.    Altered source versions must be plainly marked as such, and must
  22. //        not be misrepresented as being the original software.
  23. //    3.    This notice may not be removed or altered from any source
  24. //        distribution.
  25.  
  26. #ifndef VD2_SYSTEM_VDSTL_H
  27. #define VD2_SYSTEM_VDSTL_H
  28.  
  29. #ifdef _MSC_VER
  30.     #pragma once
  31. #endif
  32.  
  33. #include <vd2/system/vdtypes.h>
  34. #include <vd2/system/memory.h>
  35.  
  36. ///////////////////////////////////////////////////////////////////////////
  37. //
  38. //    glue
  39. //
  40. ///////////////////////////////////////////////////////////////////////////
  41.  
  42. template<class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
  43. struct vditerator {
  44. #if defined(VD_COMPILER_MSVC) && (VD_COMPILER_MSVC < 1310 || (defined(VD_COMPILER_MSVC_VC8_PSDK) || defined(VD_COMPILER_MSVC_VC8_DDK)))
  45.     typedef std::iterator<Category, T, Distance> type;
  46. #else
  47.     typedef std::iterator<Category, T, Distance, Pointer, Reference> type;
  48. #endif
  49. };
  50.  
  51. template<class Iterator, class T>
  52. struct vdreverse_iterator {
  53. #if defined(VD_COMPILER_MSVC) && (VD_COMPILER_MSVC < 1310 || (defined(VD_COMPILER_MSVC_VC8_PSDK) || defined(VD_COMPILER_MSVC_VC8_DDK)))
  54.     typedef std::reverse_iterator<Iterator, T> type;
  55. #else
  56.     typedef std::reverse_iterator<Iterator> type;
  57. #endif
  58. };
  59.  
  60. ///////////////////////////////////////////////////////////////////////////
  61.  
  62. template<class T, unsigned kDeadZone = 16>
  63. class vddebug_alloc {
  64. public:
  65.     typedef    size_t        size_type;
  66.     typedef    ptrdiff_t    difference_type;
  67.     typedef    T*            pointer;
  68.     typedef    const T*    const_pointer;
  69.     typedef    T&            reference;
  70.     typedef    const T&    const_reference;
  71.     typedef    T            value_type;
  72.  
  73.     template<class U> struct rebind { typedef vddebug_alloc<U, kDeadZone> other; };
  74.  
  75.     pointer            address(reference x) const            { return &x; }
  76.     const_pointer    address(const_reference x) const    { return &x; }
  77.  
  78.     pointer allocate(size_type n, void *p_close = 0) {
  79.         pointer p = (pointer)VDAlignedMalloc(n*sizeof(T) + 2*kDeadZone, 16);
  80.  
  81.         if (!p)
  82.             return p;
  83.  
  84.         memset((char *)p, 0xa9, kDeadZone);
  85.         memset((char *)p + kDeadZone + n*sizeof(T), 0xa9, kDeadZone);
  86.  
  87.         return (pointer)((char *)p + kDeadZone);
  88.     }
  89.  
  90.     void deallocate(pointer p, size_type n) {
  91.         char *p1 = (char *)p - kDeadZone;
  92.         char *p2 = (char *)p + n*sizeof(T);
  93.  
  94.         for(uint32 i=0; i<kDeadZone; ++i) {
  95.             VDASSERT(p1[i] == (char)0xa9);
  96.             VDASSERT(p2[i] == (char)0xa9);
  97.         }
  98.  
  99.         VDAlignedFree(p1);
  100.     }
  101.  
  102.     size_type        max_size() const throw()            { return MAX_INT - 2*kDeadZone; }
  103.  
  104.     void            construct(pointer p, const T& val)    { new((void *)p) T(val); }
  105.     void            destroy(pointer p)                    { ((T*)p)->~T(); }
  106.  
  107. #if defined(_MSC_VER) && _MSC_VER < 1300
  108.     char *            _Charalloc(size_type n)                { return rebind<char>::other::allocate(n); }
  109. #endif
  110. };
  111.  
  112. ///////////////////////////////////////////////////////////////////////////
  113.  
  114. template<class T, unsigned kAlignment = 16>
  115. class vdaligned_alloc {
  116. public:
  117.     typedef    size_t        size_type;
  118.     typedef    ptrdiff_t    difference_type;
  119.     typedef    T*            pointer;
  120.     typedef    const T*    const_pointer;
  121.     typedef    T&            reference;
  122.     typedef    const T&    const_reference;
  123.     typedef    T            value_type;
  124.  
  125.     template<class U> struct rebind { typedef vdaligned_alloc<U, kAlignment> other; };
  126.  
  127.     pointer            address(reference x) const            { return &x; }
  128.     const_pointer    address(const_reference x) const    { return &x; }
  129.  
  130.     pointer            allocate(size_type n, void *p = 0)    { return (pointer)VDAlignedMalloc(n*sizeof(T), kAlignment); }
  131.     void            deallocate(pointer p, size_type n)    { VDAlignedFree(p); }
  132.     size_type        max_size() const throw()            { return MAX_INT; }
  133.  
  134.     void            construct(pointer p, const T& val)    { new((void *)p) T(val); }
  135.     void            destroy(pointer p)                    { ((T*)p)->~T(); }
  136.  
  137. #if defined(_MSC_VER) && _MSC_VER < 1300
  138.     char *            _Charalloc(size_type n)                { return rebind<char>::other::allocate(n); }
  139. #endif
  140. };
  141.  
  142. ///////////////////////////////////////////////////////////////////////////
  143. //
  144. //    vdblock
  145. //
  146. //    vdblock<T> is similar to vector<T>, except:
  147. //
  148. //    1) May only be used with POD types.
  149. //    2) No construction or destruction of elements is performed.
  150. //    3) Capacity is always equal to size, and reallocation is performed
  151. //       whenever the size changes.
  152. //    4) Contents are undefined after a reallocation.
  153. //    5) No insertion or deletion operations are provided.
  154. //
  155. ///////////////////////////////////////////////////////////////////////////
  156.  
  157. template<class T, class A = std::allocator<T> >
  158. class vdblock : protected A {
  159. public:
  160.     typedef    T                                    value_type;
  161.     typedef    typename A::pointer                    pointer;
  162.     typedef    typename A::const_pointer            const_pointer;
  163.     typedef    typename A::reference                reference;
  164.     typedef    typename A::const_reference            const_reference;
  165.     typedef    size_t                                size_type;
  166.     typedef    ptrdiff_t                            difference_type;
  167.     typedef    pointer                                iterator;
  168.     typedef    const_pointer                        const_iterator;
  169.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  170.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  171.  
  172.     vdblock(const A& alloc = A()) : A(alloc), mpBlock(NULL), mSize(0) {}
  173.     vdblock(size_type s, const A& alloc = A()) : A(alloc), mpBlock(A::allocate(s, 0)), mSize(s) {}
  174.     ~vdblock() {
  175.         if (mpBlock)
  176.             A::deallocate(mpBlock, mSize);
  177.     }
  178.  
  179.     reference                operator[](size_type n)            { return mpBlock[n]; }
  180.     const_reference            operator[](size_type n) const    { return mpBlock[n]; }
  181.     reference                at(size_type n)                    { return n < mSize ? mpBlock[n] : throw std::length_error; }
  182.     const_reference            at(size_type n) const            { return n < mSize ? mpBlock[n] : throw std::length_error; }
  183.     reference                front()                            { return *mpBlock; }
  184.     const_reference            front() const                    { return *mpBlock; }
  185.     reference                back()                            { return mpBlock[mSize-1]; }
  186.     const_reference            back() const                    { return mpBlock[mSize-1]; }
  187.  
  188.     const_pointer            data() const    { return mpBlock; }
  189.     pointer                    data()            { return mpBlock; }
  190.  
  191.     const_iterator            begin() const    { return mpBlock; }
  192.     iterator                begin()            { return mpBlock; }
  193.     const_iterator            end() const        { return mpBlock + mSize; }
  194.     iterator                end()            { return mpBlock + mSize; }
  195.  
  196.     const_reverse_iterator    rbegin() const    { return const_reverse_iterator(end()); }
  197.     reverse_iterator        rbegin()        { return reverse_iterator(end()); }
  198.     const_reverse_iterator    rend() const    { return const_reverse_iterator(begin()); }
  199.     reverse_iterator        rend()            { return reverse_iterator(begin()); }
  200.  
  201.     bool                    empty() const        { return !mSize; }
  202.     size_type                size() const        { return mSize; }
  203.     size_type                capacity() const    { return mSize; }
  204.  
  205.     void clear() {
  206.         if (mpBlock)
  207.             A::deallocate(mpBlock, mSize);
  208.         mpBlock = NULL;
  209.         mSize = 0;
  210.     }
  211.  
  212.     void resize(size_type s) {
  213.         if (s != mSize) {
  214.             if (mpBlock) {
  215.                 A::deallocate(mpBlock, mSize);
  216.                 mpBlock = NULL;
  217.             }
  218.             mSize = s;
  219.             if (s)
  220.                 mpBlock = A::allocate(mSize, 0);
  221.         }
  222.     }
  223.  
  224.     void resize(size_type s, const T& value) {
  225.         if (s != mSize) {
  226.             if (mpBlock) {
  227.                 A::deallocate(mpBlock, mSize);
  228.                 mpBlock = NULL;
  229.             }
  230.             mSize = s;
  231.             if (s) {
  232.                 mpBlock = A::allocate(mSize, 0);
  233.                 std::fill(mpBlock, mpBlock+s, value);
  234.             }
  235.         }
  236.     }
  237.  
  238.     void swap(vdblock& x) {
  239.         std::swap(mpBlock, x.mpBlock);
  240.         std::swap(mSize, x.mSize);
  241.     }
  242.  
  243. protected:
  244.     typename A::pointer        mpBlock;
  245.     typename A::size_type    mSize;
  246.  
  247.     union PODType {
  248.         T x;
  249.     };
  250. };
  251.  
  252. ///////////////////////////////////////////////////////////////////////////
  253. //
  254. //    vdstructex
  255. //
  256. //    vdstructex describes an extensible format structure, such as
  257. //    BITMAPINFOHEADER or WAVEFORMATEX, without the pain-in-the-butt
  258. //    casting normally associated with one.
  259. //
  260. ///////////////////////////////////////////////////////////////////////////
  261.  
  262. template<class T>
  263. class vdstructex {
  264. public:
  265.     typedef size_t            size_type;
  266.     typedef T                value_type;
  267.  
  268.     vdstructex() : mpMemory(NULL), mSize(0) {}
  269.  
  270.     explicit vdstructex(size_t len) : mpMemory(NULL), mSize(0) {
  271.         resize(len);
  272.     }
  273.  
  274.     vdstructex(const T *pStruct, size_t len) : mSize(len), mpMemory((T*)malloc(len)) {
  275.         memcpy(mpMemory, pStruct, len);
  276.     }
  277.  
  278.     vdstructex(const vdstructex<T>& src) : mSize(src.mSize), mpMemory((T*)malloc(src.mSize)) {
  279.         memcpy(mpMemory, src.mpMemory, mSize);
  280.     }
  281.  
  282.     ~vdstructex() {
  283.         free(mpMemory);
  284.     }
  285.  
  286.     bool        empty() const        { return !mpMemory; }
  287.     size_type    size() const        { return mSize; }
  288.     T*            data() const        { return mpMemory; }
  289.  
  290.     T&    operator *() const    { return *(T *)mpMemory; }
  291.     T*    operator->() const    { return (T *)mpMemory; }
  292.  
  293.     bool operator==(const vdstructex& x) const {
  294.         return mSize == x.mSize && (!mSize || !memcmp(mpMemory, x.mpMemory, mSize));
  295.     }
  296.  
  297.     bool operator!=(const vdstructex& x) const {
  298.         return mSize != x.mSize || (mSize && memcmp(mpMemory, x.mpMemory, mSize));
  299.     }
  300.  
  301.     vdstructex<T>& operator=(const vdstructex<T>& src) {
  302.         assign(src.mpMemory, src.mSize);
  303.         return *this;
  304.     }
  305.  
  306.     void assign(const T *pStruct, size_type len) {
  307.         if (mSize != len)
  308.             resize(len);
  309.  
  310.         memcpy(mpMemory, pStruct, len);
  311.     }
  312.  
  313.     void clear() {
  314.         free(mpMemory);
  315.         mpMemory = NULL;
  316.         mSize = 0;
  317.     }
  318.  
  319.     void resize(size_type len) {
  320.         if (mSize != len)
  321.             mpMemory = (T *)realloc(mpMemory, mSize = len);
  322.     }
  323.  
  324. protected:
  325.     size_type    mSize;
  326.     T *mpMemory;
  327. };
  328.  
  329. ///////////////////////////////////////////////////////////////////////////
  330. //
  331. //    vdlist
  332. //
  333. //    vdlist<T> is similar to list<T*>, except:
  334. //
  335. //    1) The node structure must be embedded as a superclass of T.
  336. //     Thus, the client is in full control of allocation.
  337. //    2) Node pointers may be converted back into iterators in O(1).
  338. //
  339. ///////////////////////////////////////////////////////////////////////////
  340.  
  341. struct vdlist_node {
  342.     vdlist_node *mListNodeNext, *mListNodePrev;
  343. };
  344.  
  345. template<class T, class T_Nonconst>
  346. class vdlist_iterator : public vditerator<std::bidirectional_iterator_tag, T, ptrdiff_t>::type {
  347. public:
  348.     vdlist_iterator() {}
  349.     vdlist_iterator(vdlist_node *p) : mp(p) {}
  350.     vdlist_iterator(const vdlist_iterator<T_Nonconst, T_Nonconst>& src) : mp(src.mp) {}
  351.  
  352.     T* operator *() const {
  353.         return static_cast<T*>(mp);
  354.     }
  355.  
  356.     bool operator==(const vdlist_iterator<T, T_Nonconst>& x) const {
  357.         return mp == x.mp;
  358.     }
  359.  
  360.     bool operator!=(const vdlist_iterator<T, T_Nonconst>& x) const {
  361.         return mp != x.mp;
  362.     }
  363.  
  364.     vdlist_iterator& operator++() {
  365.         mp = mp->mListNodeNext;
  366.         return *this;
  367.     }
  368.  
  369.     vdlist_iterator& operator--() {
  370.         mp = mp->mListNodePrev;
  371.         return *this;
  372.     }
  373.  
  374.     vdlist_iterator operator++(int) {
  375.         iterator tmp(*this);
  376.         mp = mp->mListNodeNext;
  377.         return tmp;
  378.     }
  379.  
  380.     vdlist_iterator& operator--(int) {
  381.         iterator tmp(*this);
  382.         mp = mp->mListNodePrev;
  383.         return tmp;
  384.     }
  385.  
  386.     vdlist_node *mp;
  387. };
  388.  
  389. class vdlist_base {
  390. public:
  391.     typedef    vdlist_node                        node;
  392.     typedef    size_t                            size_type;
  393.     typedef    ptrdiff_t                        difference_type;
  394.  
  395.     bool empty() const {
  396.         return mAnchor.mListNodeNext == &mAnchor;
  397.     }
  398.  
  399.     size_type size() const {
  400.         node *p = { mAnchor.mListNodeNext };
  401.         size_type s = 0;
  402.  
  403.         if (p != &mAnchor)
  404.             do {
  405.                 ++s;
  406.                 p = p->mListNodeNext;
  407.             } while(p != &mAnchor);
  408.  
  409.         return s;
  410.     }
  411.  
  412.     void clear() {
  413.         mAnchor.mListNodePrev    = &mAnchor;
  414.         mAnchor.mListNodeNext    = &mAnchor;
  415.     }
  416.  
  417.     void pop_front() {
  418.         mAnchor.mListNodeNext = mAnchor.mListNodeNext->mListNodeNext;
  419.         mAnchor.mListNodeNext->mListNodePrev = &mAnchor;
  420.     }
  421.  
  422.     void pop_back() {
  423.         mAnchor.mListNodePrev = mAnchor.mListNodePrev->mListNodePrev;
  424.         mAnchor.mListNodePrev->mListNodeNext = &mAnchor;
  425.     }
  426.  
  427.     static void unlink(vdlist_node& node) {
  428.         vdlist_node& n1 = *node.mListNodePrev;
  429.         vdlist_node& n2 = *node.mListNodeNext;
  430.  
  431.         n1.mListNodeNext = &n2;
  432.         n2.mListNodePrev = &n1;
  433.     }
  434.  
  435. protected:
  436.     node    mAnchor;
  437. };
  438.  
  439. template<class T>
  440. class vdlist : public vdlist_base {
  441. public:
  442.     typedef    T*                                value_type;
  443.     typedef    T**                                pointer;
  444.     typedef    const T**                        const_pointer;
  445.     typedef    T*&                                reference;
  446.     typedef    const T*&                        const_reference;
  447.     typedef    vdlist_iterator<T, T>                        iterator;
  448.     typedef vdlist_iterator<const T, T>                    const_iterator;
  449.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  450.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  451.  
  452.     vdlist() {
  453.         mAnchor.mListNodePrev    = &mAnchor;
  454.         mAnchor.mListNodeNext    = &mAnchor;
  455.     }
  456.  
  457.     iterator begin() {
  458.         iterator it(mAnchor.mListNodeNext);
  459.         return it;
  460.     }
  461.  
  462.     const_iterator begin() const {
  463.         const_iterator it(mAnchor.mListNodeNext);
  464.         return it;
  465.     }
  466.  
  467.     iterator end() {
  468.         iterator it(&mAnchor);
  469.         return it;
  470.     }
  471.  
  472.     const_iterator end() const {
  473.         const_iterator it(&mAnchor);
  474.         return it;
  475.     }
  476.  
  477.     reverse_iterator rbegin() {
  478.         return reverse_iterator(begin());
  479.     }
  480.  
  481.     const_reverse_iterator rbegin() const {
  482.         return const_reverse_iterator(begin());
  483.     }
  484.  
  485.     reverse_iterator rend() {
  486.         return reverse_iterator(end);
  487.     }
  488.  
  489.     const_reverse_iterator rend() const {
  490.         return const_reverse_iterator(end());
  491.     }
  492.  
  493.     const value_type front() const {
  494.         return static_cast<T *>(mAnchor.mListNodeNext);
  495.     }
  496.  
  497.     const value_type back() const {
  498.         return static_cast<T *>(mAnchor.mListNodePrev);
  499.     }
  500.  
  501.     iterator find(T *p) {
  502.         iterator it(mAnchor.mListNodeNext);
  503.  
  504.         if (it.mp != &mAnchor)
  505.             do {
  506.                 if (it.mp == static_cast<node *>(p))
  507.                     break;
  508.  
  509.                 it.mp = it.mp->mListNodeNext;
  510.             } while(it.mp != &mAnchor);
  511.  
  512.         return it;
  513.     }
  514.  
  515.     const_iterator find(T *p) const {
  516.         const_iterator it(mAnchor.mListNodeNext);
  517.  
  518.         if (it.mp != &mAnchor)
  519.             do {
  520.                 if (it.mp == static_cast<node *>(p))
  521.                     break;
  522.  
  523.                 it.mp = it.mp->mListNodeNext;
  524.             } while(it.mp != &mAnchor);
  525.  
  526.         return it;
  527.     }
  528.  
  529.     iterator fast_find(T *p) {
  530.         iterator it(p);
  531.         return it;
  532.     }
  533.  
  534.     const_iterator fast_find(T *p) const {
  535.         iterator it(p);
  536.     }
  537.  
  538.     void push_front(T *p) {
  539.         node& n = *p;
  540.         n.mListNodePrev = &mAnchor;
  541.         n.mListNodeNext = mAnchor.mListNodeNext;
  542.         n.mListNodeNext->mListNodePrev = &n;
  543.         mAnchor.mListNodeNext = &n;
  544.     }
  545.  
  546.     void push_back(T *p) {
  547.         node& n = *p;
  548.         n.mListNodeNext = &mAnchor;
  549.         n.mListNodePrev = mAnchor.mListNodePrev;
  550.         n.mListNodePrev->mListNodeNext = &n;
  551.         mAnchor.mListNodePrev = &n;
  552.     }
  553.  
  554.     iterator erase(T *p) {
  555.         return erase(fast_find(p));
  556.     }
  557.  
  558.     iterator erase(iterator it) {
  559.         node& n = *it.mp;
  560.  
  561.         n.mListNodePrev->mListNodeNext = n.mListNodeNext;
  562.         n.mListNodeNext->mListNodePrev = n.mListNodePrev;
  563.  
  564.         it.mp = n.mListNodeNext;
  565.         return it;
  566.     }
  567.  
  568.     iterator erase(iterator i1, iterator i2) {
  569.         node& np = *i1.mp->mListNodePrev;
  570.         node& nn = *i2.mp;
  571.  
  572.         np.mListNodeNext = &nn;
  573.         nn.mListNodePrev = &np;
  574.  
  575.         return i2;
  576.     }
  577.  
  578.     void insert(iterator dst, T *src) {
  579.         node& ns = *src;
  580.         node& nd = *dst.mp;
  581.  
  582.         ns.mListNodeNext = &nd;
  583.         ns.mListNodePrev = nd.mListNodePrev;
  584.         nd.mListNodePrev->mListNodeNext = &ns;
  585.         nd.mListNodePrev = &ns;
  586.     }
  587.  
  588.     void insert(iterator dst, iterator i1, iterator i2) {
  589.         if (i1 != i2) {
  590.             node& np = *dst.mp->mListNodePrev;
  591.             node& nn = *dst.mp;
  592.             node& n1 = *i1.mp;
  593.             node& n2 = *i2.mp->mListNodePrev;
  594.  
  595.             np.mListNodeNext = &n1;
  596.             n1.mListNodePrev = &np;
  597.             n2.mListNodeNext = &nn;
  598.             nn.mListNodePrev = &n2;
  599.         }
  600.     }
  601.  
  602.     void splice(iterator dst, vdlist<T>& srclist) {
  603.         insert(dst, srclist.begin(), srclist.end());
  604.         srclist.clear();
  605.     }
  606.  
  607.     void splice(iterator dst, vdlist<T>& srclist, iterator src) {
  608.         T *v = *src;
  609.         srclist.erase(src);
  610.         insert(dst, v);
  611.     }
  612.  
  613.     void splice(iterator dst, vdlist<T>& srclist, iterator i1, iterator i2) {
  614.         if (dst.mp != i1.mp && dst.mp != i2.mp) {
  615.             srclist.erase(i1, i2);
  616.             insert(dst, i1, i2);
  617.         }
  618.     }
  619. };
  620.  
  621. ///////////////////////////////////////////////////////////////////////////////
  622.  
  623. template<class T, class A = std::allocator<T> >
  624. class vdfastvector {
  625. public:
  626.     typedef    T                    value_type;
  627.     typedef    T*                    pointer;
  628.     typedef    const T*            const_pointer;
  629.     typedef    T&                    reference;
  630.     typedef    const T&            const_reference;
  631.     typedef    size_t                size_type;
  632.     typedef    ptrdiff_t            difference_type;
  633.     typedef    pointer                iterator;
  634.     typedef const_pointer        const_iterator;
  635.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  636.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  637.  
  638. public:
  639.     vdfastvector() {
  640.         m.begin = NULL;
  641.         m.end = NULL;
  642.         m.eos = NULL;
  643.     }
  644.  
  645.     vdfastvector(size_type len) {
  646.         m.begin = m.allocate(len, NULL);
  647.         m.end = m.begin + len;
  648.         m.eos = m.begin + len;
  649.     }
  650.  
  651.     vdfastvector(size_type len, const T& fill) {
  652.         m.begin = m.allocate(len, NULL);
  653.         m.end = m.begin + len;
  654.         m.eos = m.begin + len;
  655.  
  656.         std::fill(m.begin, m.end, fill);
  657.     }
  658.  
  659.     vdfastvector(const vdfastvector& x) {
  660.         size_type n = x.m.end - x.m.begin;
  661.         m.begin = m.allocate(n, NULL);
  662.         m.end = m.begin + n;
  663.         m.eos = m.end;
  664.         memcpy(m.begin, x.m.begin, sizeof(T) * n);
  665.     }
  666.  
  667.     vdfastvector(const value_type *p, const value_type *q) {
  668.         m.begin = NULL;
  669.         m.end = NULL;
  670.         m.eos = NULL;
  671.  
  672.         assign(p, q);
  673.     }
  674.  
  675.     ~vdfastvector() {
  676.         if (m.begin)
  677.             m.deallocate(m.begin, m.eos - m.begin);
  678.     }
  679.  
  680.     vdfastvector& operator=(const vdfastvector& x) {
  681.         if (this != &x) {
  682.             m.end = m.begin;
  683.             resize(x.m.end - x.m.begin);
  684.             memcpy(m.begin, x.m.begin, (char *)x.m.end - (char *)x.m.begin);
  685.         }
  686.         return *this;
  687.     }
  688.  
  689. public:
  690.     bool        empty() const        { return m.begin == m.end; }
  691.     size_type    size() const        { return size_type(m.end - m.begin); }
  692.     size_type    capacity() const    { return size_type(m.eos - m.begin); }
  693.  
  694.     pointer            data()            { return m.begin; }
  695.     const_pointer    data() const    { return m.begin; }
  696.  
  697.     iterator        begin()            { return m.begin; }
  698.     const_iterator    begin() const    { return m.begin; }
  699.     iterator        end()            { return m.end; }
  700.     const_iterator    end() const        { return m.end; }
  701.  
  702.     reverse_iterator        rbegin()        { return reverse_iterator(m.begin); }
  703.     const_reverse_iterator    rbegin() const    { return const_reverse_iterator(m.begin); }
  704.     reverse_iterator        rend()            { return reverse_iterator(m.end); }
  705.     const_reverse_iterator    rend() const    { return const_reverse_iterator(m.end); }
  706.  
  707.     reference        front()            { return *m.begin; }
  708.     const_reference    front() const    { return *m.begin; }
  709.     reference        back()            { VDASSERT(m.begin != m.end); return m.end[-1]; }
  710.     const_reference    back() const    { VDASSERT(m.begin != m.end); return m.end[-1]; }
  711.  
  712.     reference            operator[](size_type n)            { VDASSERT(n < size_type(m.end - m.begin)); return m.begin[n]; }
  713.     const_reference        operator[](size_type n) const    { VDASSERT(n < size_type(m.end - m.begin)); return m.begin[n]; }
  714.  
  715. public:
  716.     T *alloc(size_type n) {
  717.         size_type offset = (size_type)(m.end - m.begin);
  718.         resize(offset + n);
  719.         return m.begin + offset;
  720.     }
  721.  
  722.     void assign(const T *p1, const T *p2) {
  723.         if (m.begin) {
  724.             m.deallocate(m.begin, m.eos - m.begin);
  725.             m.begin = NULL;
  726.             m.end = NULL;
  727.             m.eos = NULL;
  728.         }
  729.  
  730.         resize(p2 - p1);
  731.         memcpy(m.begin, p1, (char *)p2 - (char *)p1);
  732.     }
  733.  
  734.     void clear() {
  735.         m.end = m.begin;
  736.     }
  737.  
  738.     iterator erase(iterator it) {
  739.         VDASSERT(it - m.begin < m.end - m.begin);
  740.  
  741.         memmove(it, it+1, (char *)m.end - (char *)(it+1));
  742.  
  743.         --m.end;
  744.  
  745.         return it;
  746.     }
  747.  
  748.     iterator erase(iterator it1, iterator it2) {
  749.         VDASSERT(it1 - m.begin <= m.end - m.begin);
  750.         VDASSERT(it2 - m.begin <= m.end - m.begin);
  751.         VDASSERT(it1 <= it2);
  752.  
  753.         memmove(it1, it2, (char *)m.end - (char *)it2);
  754.  
  755.         m.end -= (it2 - it1);
  756.  
  757.         return it1;
  758.     }
  759.  
  760.     iterator insert(iterator it, const T& value) {
  761.         const T temp(value);        // copy in case value is inside container.
  762.  
  763.         if (m.end == m.eos) {
  764.             difference_type delta = it - m.begin;
  765.             _reserve_always_add_one();
  766.             it = m.begin + delta;
  767.         }
  768.  
  769.         memmove(it+1, it, sizeof(T) * (m.end - it));
  770.         *it = temp;
  771.         ++m.end;
  772.         VDASSERT(m.end <= m.eos);
  773.  
  774.         return it;
  775.     }
  776.  
  777.     iterator insert(iterator it, size_type n, const T& value) {
  778.         const T temp(value);        // copy in case value is inside container.
  779.  
  780.         ptrdiff_t bytesToInsert = n * sizeof(T);
  781.  
  782.         if ((char *)m.eos - (char *)m.end < bytesToInsert) {
  783.             difference_type delta = it - m.begin;
  784.             _reserve_always_add(bytesToInsert);
  785.             it = m.begin + delta;
  786.         }
  787.  
  788.         memmove((char *)it + bytesToInsert, it, (char *)m.end - (char *)it);
  789.         for(size_t i=0; i<n; ++i)
  790.             *it++ = temp;
  791.         m.end += n;
  792.         VDASSERT(m.end <= m.eos);
  793.         return it;
  794.     }
  795.  
  796.     iterator insert(iterator it, const T *p1, const T *p2) {
  797.         ptrdiff_t elementsToCopy = p2 - p1;
  798.         ptrdiff_t bytesToCopy = (char *)p2 - (char *)p1;
  799.  
  800.         if ((char *)m.eos - (char *)m.end < bytesToCopy) {
  801.             difference_type delta = it - m.begin;
  802.             _reserve_always_add(bytesToCopy);
  803.             it = m.begin + delta;
  804.         }
  805.  
  806.         memmove((char *)it + bytesToCopy, it, (char *)m.end - (char *)it);
  807.         memcpy(it, p1, bytesToCopy);
  808.         m.end += elementsToCopy;
  809.         VDASSERT(m.end <= m.eos);
  810.         return it;
  811.     }
  812.  
  813.     void push_back() {
  814.         if (m.end == m.eos)
  815.             _reserve_always_add_one();
  816.  
  817.         ++m.end;
  818.     }
  819.  
  820.     void push_back(const T& value) {
  821.         const T temp(value);        // copy in case value is inside container.
  822.  
  823.         if (m.end == m.eos)
  824.             _reserve_always_add_one();
  825.  
  826.         *m.end++ = temp;
  827.     }
  828.  
  829.     void pop_back() {
  830.         VDASSERT(m.begin != m.end);
  831.         --m.end;
  832.     }
  833.  
  834.     void resize(size_type n) {
  835.         if (n*sizeof(T) > size_type((char *)m.eos - (char *)m.begin))
  836.             _reserve_always_amortized(n);
  837.  
  838.         m.end = m.begin + n;
  839.     }
  840.  
  841.     void resize(size_type n, const T& value) {
  842.         const T temp(value);
  843.  
  844.         if (n*sizeof(T) > size_type((char *)m.eos - (char *)m.begin)) {
  845.             _reserve_always_amortized(n);
  846.         }
  847.  
  848.         const iterator newEnd(m.begin + n);
  849.         if (newEnd > m.end)
  850.             std::fill(m.end, newEnd, temp);
  851.         m.end = newEnd;
  852.     }
  853.  
  854.     void reserve(size_type n) {
  855.         if (n*sizeof(T) > size_type((char *)m.eos - (char *)m.begin))
  856.             _reserve_always(n);
  857.     }
  858.  
  859.     void swap(vdfastvector& x) {
  860.         T *p;
  861.  
  862.         p = m.begin;        m.begin = x.m.begin;        x.m.begin = p;
  863.         p = m.end;            m.end = x.m.end;            x.m.end = p;
  864.         p = m.eos;            m.eos = x.m.eos;            x.m.eos = p;
  865.     }
  866.  
  867. protected:
  868. #ifdef _MSC_VER
  869.     __declspec(noinline)
  870. #endif
  871.     void _reserve_always_add_one() {
  872.         _reserve_always((m.eos - m.begin) * 2 + 1);
  873.     }
  874.  
  875. #ifdef _MSC_VER
  876.     __declspec(noinline)
  877. #endif
  878.     void _reserve_always_add(size_type n) {
  879.         _reserve_always((m.eos - m.begin) * 2 + n);
  880.     }
  881.  
  882. #ifdef _MSC_VER
  883.     __declspec(noinline)
  884. #endif
  885.     void _reserve_always(size_type n) {
  886.         size_type oldSize = m.end - m.begin;
  887.         T *oldStorage = m.begin;
  888.         T *newStorage = m.allocate(n, NULL);
  889.  
  890.         memcpy(newStorage, m.begin, (char *)m.end - (char *)m.begin);
  891.         m.deallocate(oldStorage, m.eos - m.begin);
  892.         m.begin = newStorage;
  893.         m.end = newStorage + oldSize;
  894.         m.eos = newStorage + n;
  895.     }
  896.  
  897. #ifdef _MSC_VER
  898.     __declspec(noinline)
  899. #endif
  900.     void _reserve_always_amortized(size_type n) {
  901.         size_type nextCapacity = (size_type)((m.eos - m.begin)*2);
  902.  
  903.         if (nextCapacity < n)
  904.             nextCapacity = n;
  905.  
  906.         _reserve_always(nextCapacity);
  907.     }
  908.  
  909.     struct : A {
  910.         T *begin;
  911.         T *end;
  912.         T *eos;
  913.     } m;
  914.  
  915.     union TrivialObjectConstraint {
  916.         T m;
  917.     };
  918. };
  919.  
  920.  
  921. #endif
  922.